package top.hkyzf.study.leetcode.array;

import org.junit.Test;

/**
 * description: 
 * @author zhufeng
 * @date 2023/4/3 15:04
 * @version V1.0
 */
public class 交换一次的先前排列_1053 {

    @Test
    public void testPrevPermOpt () {
        int[] arr = {3,1,1,3};
        int[] ints = prevPermOpt1(arr);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public int[] prevPermOpt1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int first = arr.length-2;
        for (int second = first+1; second <= arr.length-1; second++) {
            if (arr[first] > arr[second]) {
                for (int i = second+1; i <= arr.length - 1; i++) {
                    if (arr[second] < arr[i] && arr[first] > arr[i]) {
                        second = i;
                    }
                }
                int temp = arr[first];
                arr[first] = arr[second];
                arr[second] = temp;
                return arr;
            }
            if (first == 0) {
                break;
            }
            if (second == arr.length-1) {
                first--;
                second = first;
            }
        }
        return arr;
    }
}
